<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>字符串查找树</title>
  </head>
  <body>
    <script>
      class Trie {
        constructor() {
          this.root = Object.create(null);
        }
        insert(word) {
          let node = this.root;
          for (let i = 0; i < word.length; i++) {
            const c = word[i];
            if (!node[c]) {
              node[c] = Object.create(null);
            }
            node = node[c];
          }
          if (!node.$) {
            node.$ = 0;
          }
          node.$++;
        }
        most() {
          let max = 0;
          let maxWord = "";

          const visit = (node, word) => {
            if (node.$ && node.$ > max) {
              max = node.$;
              maxWord = word;
            }
            for (const item in node) {
              if (Object.hasOwnProperty.call(node, item)) {
                const n = node[item];
                visit(n, word + item);
              }
            }
          }; 
          visit(this.root, maxWord);
          return {
            max,
            maxWord
          };
        }
      }
      function createRandomString(length) {
        var word = "";
        for (var i = 0; i < length; i++) {
          word += String.fromCharCode(Math.random() * 26 + "a".charCodeAt());
        }
        return word;
      }
      const t = new Trie();
      for (var i = 0; i < 100; i++) {
        const word = createRandomString(6);
        t.insert(word);
      }
      const root = t.root;
      const most = t.most();
      console.log(t.root, most);
    </script>
  </body>
</html>
